//package leetcode;
//
//class Solution {
//    public boolean exist(char[][] board, String word) {
//        int with = board.length;
//        int high = board[0].length;
//        boolean[][] visited = new boolean[with][high];
//
//        for (int i = 0; i < with; i++) {
//            for (int j = 0; j < high; j++) {
//                boolean flag = check(board, visited, i, j, word, 0);
//                if (flag) {
//                    return true;
//                }
//            }
//        }
//        return false;
//    }
//
//    public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
//        if (board[i][j] != s.charAt(k)) {
//            return false;
//        } else if (k == s.length() - 1) {
//            return true;
//        }
//        visited[i][j] = true;
//        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
//        boolean result = false;
//        for (int[] dir : directions) {
//            int newi = i + dir[0];
//            int newj = j + dir[1];
//            if (newi >= 0 && newi < board.length && newj < board[0].length) {
//                if (!visited[newi][newj]) {
//                    boolean flag = check(board, visited, newi, newj, s, k + 1);
//                    if (flag) {
//                        result = true;
//                        break;
//                    }
//                }
//            }
//        }
//        visited[i][j] = false;
//        return result;
//
//    }
//}
//
//public class Test2 {
//    public static void main(String[] args) {
//        char[][] array = new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
//        Solution solution = new Solution();
//        if (solution.exist(array, "BCCED")) {
//            System.out.println("true");
//        }else {
//            System.out.println("false");
//        }
//
//    }
//}
